1383C - String Transformation 2 - CodeForces Solution

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx,avx,avx2")
// #define ATC
#define LL long long
#define eb emplace_back
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;

#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif

constexpr int N = 1e5 + 500;
int n;
string s, t;

inline void slv () {
	cin >> n >> s >> t;
	vector b(20, 0), par(20, 0);
	iota(par.begin(), par.end(), 0);
	int tot = 20;
	auto find = [&](int x, auto self) -> int { 
		return x == par[x] ? x : par[x] = self(par[x], self);
	};
	auto merge = [&](int x, int y) -> void {
		x = find(x, find), y = find(y, find);
		if (x == y) return;
		par[x] = y;
		--tot;
	};
	for (int i = 0; i < n; i++) {
		if (s[i] != t[i]) {
			int u = s[i] - 'a', v = t[i] - 'a';
			b[u] |= (1 << v);
			merge(u, v);
		}
	}
	vector f(1 << 20, 0);
	f[0] = 1;
	for (int s = 0; s < (1 << 20); s++) {
		if (!f[s]) continue;
		for (int i = 0; i < 20; i++) {
			if (!(b[i] & s) && !(s >> i & 1)) {
				f[s | (1 << i)] = 1;
			}
		}
	}
	int as = 0;
	for (int i = 0; i < (1 << 20); i++) {
		if (f[i]) {
			as = max(as, __builtin_popcount(i));
		}
	}
	cout << 40 - as - tot << '\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) slv();
}
// I love WHQ!